package com.leetcode.offer.chapter3;

/**
 * @author Dennis Li
 * @date 2020/7/13 9:30
 */
public class RegexMatch_19 {

    // 动态规划难题！！！ -- 注意理解
    public boolean isMatch(String s, String p) {
        char[] str = s.toCharArray();
        char[] pat = p.toCharArray();
        int i = 0, j = 0;
        while (i < str.length) {
            if (j == pat.length) return false;
            if (pat[j] == '*') {
                char repeat = pat[j - 1];
                j++; // 先赋值，再自增
                while (i < str.length && str[i] == repeat) {
                    if (j < pat.length && pat[j] == repeat) j++;
                    i++;
                }
            } else if (pat[j] != str[i]) {
                if (j < pat.length - 1) {
                    if (pat[j + 1] != '*' && pat[j] != '.')
                        return false;
                    else if (pat[j + 1] == '*' && pat[j] == '.')
                        return true;
                    else if (pat[j + 1] == '*' && pat[j] != '.')
                        j += 2;
                } else {
                    if (pat[j] != '.') return false;
                }
            } else {
                i++;
                j++;
            }
        }
        return true;
    }

    public boolean match(String s, String p) {
        char[] str = s.toCharArray();
        char[] pat = p.toCharArray();
        int m = str.length, n = pat.length;

        // 转移方程的定义f(i)(j) -- 代表字符串前i个和模式串的前j个字符是匹配的
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 解决空串和非空正则的匹配
        // "" "c*"是匹配的； 同理 "" "c*v*" 也是匹配的
        for (int i = 1; i <= n; i++) {
            if (pat[i - 1] == '*')
                dp[0][i] = dp[0][i - 2];
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str[i - 1] == pat[j - 1] || pat[j - 1] == '.')
                    // 如果相等或者为'.' -- 那么直接就是之前的结果
                    // 之前匹配，那么现在也是匹配的
                    dp[i][j] = dp[i - 1][j - 1];
                else if (pat[j - 1] == '*') {
                    // 如果出现了 *，那么判断*的前一个是否相等，或者是否为'.'
                    if (pat[j - 2] == str[i - 1] || pat[j - 2] == '.') {
                        // 三种情况任一满足即可
                        // dp[i][j - 2] -- *个数为0
                        // dp[i][j-1] -- 下一个位置i是否满足
                        // dp[i - 1][j] --
                        dp[i][j] |= dp[i][j - 1] | dp[i - 1][j] | dp[i][j - 2];
                    }else{
                        // * 视为0
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String str1 = "mississippi";
        String str2 = "mis*is*p*.";
        System.out.println(new RegexMatch_19().isMatch(str1, str2));
    }

}
